class Solution {
    int ret;
    public int findKthLargest(int[] nums, int k) {
        quick(nums, 0, nums.length - 1, k);
        return ret;
    }
    public void quick(int[] nums, int s, int e, int k) {
        if(s >= e) {
            ret = nums[s];
            return;
        }
        //随机选择基准元素
        int key = nums[new Random().nextInt(e - s + 1) + s];

        //根据基准元素，使数组分三块
        int left = s - 1, right = e + 1, i = s;
        while(i < right) {
            if(nums[i] < key) 
                swap(nums, ++left, i++);
            else if(nums[i] == key) 
                i++;
            else 
                swap(nums,--right, i);
        }

        //分类讨论
        //[s,left], [left + 1, right - 1], [rigth, e]
        int b = right - left - 1, c = e - right + 1;
        if(c >= k) {
            quick(nums, right, e, k);
        }else if (b + c >= k) {
            ret = key;
            return;
        }else {
            quick(nums, s, left, k - b - c);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}